package 数组;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import 二叉树.TreeNode;

public class _653_两数之和_IV_输入二叉搜索树 {

	public static void main(String[] args) {
		// root = [5,3,6,2,4,null,7], k = 9
		TreeNode node7 = new TreeNode(9,null,null);
		TreeNode node4 = new TreeNode(4);
		TreeNode node2 = new TreeNode(2,null,null);
		TreeNode node6 = new TreeNode(6,null,node7);
		TreeNode node3 = new TreeNode(3,node2,node4);
		TreeNode node = new TreeNode(5,node3,node6);
		_653_两数之和_IV_输入二叉搜索树 test = new _653_两数之和_IV_输入二叉搜索树();
		System.out.println(test.findTarget(node, 9));
	}
	
	public boolean findTarget(TreeNode root, int k) {
		Set<Integer> set = new HashSet<>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if(set.contains(k - node.val)) return true;
			set.add(node.val);
			if(node.left != null) {
				queue.offer(node.left);
			}
			if(node.right != null) {
				queue.offer(node.right);
			}
		}
		return false;
	}
	
	public boolean findTarget01(TreeNode root, int k) {
		Set<Integer> set = new HashSet<>();
		return find(root, k, set);
	}
	
	 public boolean find(TreeNode root, int k,Set<Integer> set) {
		 if(root == null) return false;
		 if(set.contains(k - root.val)) return true;
		 set.add(root.val);
		 return find(root.left, k, set) || find(root.right, k, set);
	 }

}
